Two-factor authentication is ubiquitous in contemporary authentication systems. One of the methods used for 2FA are the so-called authenticator apps. Whenever the server needs to validate that it really is you who is trying to log in, you just open the app and it magically produces a code which you can enter and the server magically accepts it! Furthermore, a new code appears after a given period of time, usually 30-60 seconds.
But how does the authenticator app know what code to give and how does the server know when the code is correct?
The code generated by the authenticator app is called a one-time password. Whenever you set up 2FA on your account for the first time, you will be asked to either scan a QR code with the application or manually enter an alphanumeric string into the authenticator application, called a seed, which is then stored on both the server and in your authenticator app. This seed should never be shared with anyone else.
From then on, one-time passwords are generated using a pseudorandom function generator (PRFG). One example procedure for a one-time password authentication uses a publicly known one-bit PRFG
When the server receives your code, it generates its own code by using the secret seed
In practice, one-time password systems use PRFGs which output more than a single bit.
What does it mean for a one-time password system to be secure? Well, the server either rejects or accepts your log in depending on the code you sent it. An adversary won't have access to the secret seed, so the most basic strategy, which is always possible to do, is to attempt to guess the code. The probability of the adversary just guessing the code is
A one-time password system with a seed $s$ of length $S$, base index $i_0 \in \{0,1,..., 2^S - 1\}$ and security parameter $l$ is *secure* if for every efficient adversary $\textit{Eve}(i_0: \textbf{int}[0..2^S], l: \textbf{int}) \to \textbf{str}[l]$ who knows the base index and the security parameter, the probability that $\textit{Eve}$ will be authenticated by the server without knowledge of the secret seed is at most $\frac{1}{2^l} + \epsilon(S)$ for some neglgigible $\epsilon$, i.e.
$$\Pr[\textit{Server}(\textit{Eve}(i_0, l)) = \text{ authenticated }] \le \frac{1}{2^l} + \epsilon(S)$$
A one-time password system is secure if there is no adversary that, given the base index $i_0$ and security parameter $l$, can guess what code the server will generate with probability marginally better than $\frac{1}{2^l}$.
From this definition we see that the security of a one-time password heavily depends on the security of the parameter
Indeed, using this definition, we can prove that the aforementioned one-time password system is secure so long as the PRFG it uses is.
TODO
It is paramount that the same base index is never used twice in order to thwart replay attacks. If an adversary eavesdrops on the connection between you and the server, they can store the base index and the code you send to the server in every two-factor authentication session.
The adversary can later try to authenticate and if the server sends them a base index which they previously recorded from you, then they also know the correct code for this index and will successfully authenticate.
The same base index should never be reused.
A random base index is just a fairly easy way to achieve this non-repetition of indices because even if the index is just 128 bits in length, the probability that the same index will be reused is